{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Length of Pair Chain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLongestChain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长数对链"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由&nbsp;<code>n</code>&nbsp;个数对组成的数对数组&nbsp;<code>pairs</code>&nbsp;，其中&nbsp;<code>pairs[i] = [left<sub>i</sub>, right<sub>i</sub>]</code>&nbsp;且&nbsp;<code>left<sub>i</sub>&nbsp;&lt; right<sub>i</sub></code><sub> 。</sub></p>\n",
    "\n",
    "<p>现在，我们定义一种 <strong>跟随</strong> 关系，当且仅当&nbsp;<code>b &lt; c</code>&nbsp;时，数对&nbsp;<code>p2 = [c, d]</code>&nbsp;才可以跟在&nbsp;<code>p1 = [a, b]</code>&nbsp;后面。我们用这种形式来构造 <strong>数对链</strong> 。</p>\n",
    "\n",
    "<p>找出并返回能够形成的 <strong>最长数对链的长度</strong> 。</p>\n",
    "\n",
    "<p>你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>pairs =&nbsp;[[1,2], [2,3], [3,4]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最长的数对链是 [1,2] -&gt; [3,4] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pairs = [[1,2],[7,8],[4,5]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>最长的数对链是 [1,2] -&gt; [4,5] -&gt; [7,8] 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == pairs.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>-1000 &lt;= left<sub>i</sub>&nbsp;&lt; right<sub>i</sub>&nbsp;&lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-length-of-pair-chain](https://leetcode.cn/problems/maximum-length-of-pair-chain/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-length-of-pair-chain](https://leetcode.cn/problems/maximum-length-of-pair-chain/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[3,4]]', '[[1,2],[7,8],[4,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPairChain(self, i: int, pairs: List[List[int]], n: int, memo: List[int]) -> int:\n",
    "        if memo[i] != 0:\n",
    "            return memo[i]\n",
    "        memo[i] = 1\n",
    "        for j in range(i + 1, n):\n",
    "            if pairs[i][1] < pairs[j][0]:\n",
    "                memo[i] = max(memo[i], 1 + self.longestPairChain(j, pairs, n, memo))\n",
    "        return memo[i]\n",
    "\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        n = len(pairs)\n",
    "        pairs.sort()\n",
    "        memo = [0] * n\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, self.longestPairChain(i, pairs, n, memo))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(pairs) == 0:\n",
    "            return 0\n",
    "        pairs = sorted(pairs,key=lambda x:x[1])\n",
    "        dp = [1 for _ in pairs]\n",
    "        for i in range(1,len(pairs)):\n",
    "            imin = pairs[i][0]\n",
    "            maxj = 0\n",
    "            maxnum = 0\n",
    "            for j in range(i):\n",
    "                if dp[j]>maxnum and pairs[j][1]<imin:\n",
    "                    maxnum = dp[j]\n",
    "                    maxj = j\n",
    "            dp[i] = dp[maxj] + 1 if pairs[maxj][1]<imin else 1\n",
    "        \n",
    "        return max(dp)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(pairs) == 0:\n",
    "            return 0\n",
    "        pairs = sorted(pairs,key=lambda x:x[1])\n",
    "        dp = [1 for _ in pairs]\n",
    "        for i in range(1,len(pairs)):\n",
    "            imin = pairs[i][0]\n",
    "            maxj = 0\n",
    "            maxnum = 0\n",
    "            for j in range(i):\n",
    "                if dp[j]>maxnum and pairs[j][1]<imin:\n",
    "                    maxnum = dp[j]\n",
    "                    maxj = j\n",
    "            dp[i] = dp[maxj] + 1 if pairs[maxj][1]<imin else 1\n",
    "        \n",
    "        return max(dp)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ret=0\n",
    "        pairs.sort(key=lambda x:x[1])\n",
    "        while len(pairs)>0:\n",
    "            k=pairs[0]\n",
    "            pairs=pairs[1:]\n",
    "            ret=ret+1\n",
    "            pairs=[[i,j] for [i,j] in pairs if i>k[1]]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        pairs.sort(key=lambda x: (x[1], x[0]))\n",
    "        q = -float(\"inf\")\n",
    "        res = 0\n",
    "        for p in pairs:\n",
    "            if q < p[0]:\n",
    "                res += 1\n",
    "                q = p[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        mix_r = pairs[0][1]\n",
    "        idx = 0\n",
    "        tmp_idx = 0\n",
    "        tmp = []\n",
    "        for item in pairs:\n",
    "            if item[1] < mix_r:\n",
    "                mix_r = item[1]\n",
    "                tmp_idx = idx\n",
    "            idx = idx + 1\n",
    "        tmp.append(pairs[tmp_idx])\n",
    "        del pairs[tmp_idx]\n",
    "        \n",
    "        flag = True\n",
    "        while flag:\n",
    "            mix_r = False\n",
    "            index = 0\n",
    "            for k in range(len(pairs)):\n",
    "                if len(pairs) < 1:\n",
    "                    break\n",
    "                if pairs[k][0] > tmp[len(tmp) - 1][1]:\n",
    "                    \n",
    "                    if mix_r is False or pairs[k][1] < mix_r:\n",
    "                        print(pairs[k],  tmp[len(tmp) - 1])\n",
    "                        mix_r = pairs[k][1]\n",
    "                        index = k\n",
    "            if mix_r is False:\n",
    "                flag = False\n",
    "            else:\n",
    "                tmp.append(pairs[index])\n",
    "        # print(tmp)\n",
    "        return len(tmp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        pairs.sort(key=lambda x: x[1])\n",
    "        q = -float(\"inf\")\n",
    "        res = 0\n",
    "        for p in pairs:\n",
    "            if q < p[0]:\n",
    "                res += 1\n",
    "                q = p[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        pairs.sort(key=lambda x: x[1])\n",
    "        q = -float(\"inf\")\n",
    "        res = 0\n",
    "        for p in pairs:\n",
    "            if q < p[0]:\n",
    "                res += 1\n",
    "                q = p[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        \"\"\"\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        pairs.sort(key=lambda x: (x[1], x[0]))\n",
    "        q = -float(\"inf\")\n",
    "        res = 0\n",
    "        for p in pairs:\n",
    "            if q < p[0]:\n",
    "                res += 1\n",
    "                q = p[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs=sorted(pairs,key=lambda x:x[1])\n",
    "        dp=[1]*len(pairs)\n",
    "        for i in range(1,len(pairs)):\n",
    "            dp[i]=dp[i-1]\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if pairs[j][1]<pairs[i][0]:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "                    break\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 这个题目和前面的最长上升子序列差不多，都是动态规划来解\n",
    "# 这个是可以用所有的顺序，卡到这不知道怎么解了\n",
    "# 题解是先将这个数组排序，这样子就可以首字母到后面越来越大了\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs):\n",
    "        length = len(pairs)\n",
    "        if length == 0:return 0\n",
    "        if length == 1:return 1\n",
    "        pairs.sort()\n",
    "        # 直接用这个来排序\n",
    "        dp = [1]*length\n",
    "        for i in range(length):\n",
    "            for j in range(i):\n",
    "                if pairs[j][1] < pairs[i][0]:\n",
    "                    dp[i] = max(dp[i],dp[j] + 1)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs) -> int:\n",
    "        if len(pairs) == 0:\n",
    "            return 0\n",
    "        pairs.sort(key=lambda x: (x[0], x[1]))\n",
    "        previous = pairs[0]\n",
    "        count = 1\n",
    "        for i in range(1, len(pairs)):\n",
    "            if pairs[i][0] >= previous[0] and pairs[i][1] <= previous[1]:\n",
    "                previous = pairs[i]\n",
    "            elif pairs[i][0] > previous[1]:\n",
    "                count += 1\n",
    "                previous = pairs[i]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        \n",
    "        cur, ans = float('-inf'), 0\n",
    "        \n",
    "        for x,y in sorted(pairs, key = operator.itemgetter(1)):\n",
    "            if cur < x:\n",
    "                cur = y\n",
    "                ans += 1\n",
    "                \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        cur = float('-inf')\n",
    "        ans = 0\n",
    "\n",
    "        for x, y in sorted(pairs ,key = lambda x: x[1]):\n",
    "            if cur < x:\n",
    "                cur = y\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        if not pairs:\n",
    "            return 1\n",
    "        if  len(pairs)==1:\n",
    "            return 1\n",
    "        n=len(pairs)\n",
    "        res=1\n",
    "        pairs.sort(key=lambda x:(x[1],x[0]))\n",
    "        tmp=pairs[0][1]\n",
    "        for i in range(1,n):\n",
    "            if pairs[i][0]>tmp:\n",
    "                res+=1\n",
    "                tmp=pairs[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs.sort(key=lambda x:x[1])\n",
    "        end=-float(\"inf\")\n",
    "        re=0\n",
    "        for i in pairs:\n",
    "            if i[0]>end:\n",
    "                end=i[1]\n",
    "                re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs.sort(key=lambda x:x[1])\n",
    "        res=1\n",
    "        ed=pairs[0][1]\n",
    "        for pair in pairs:\n",
    "            if pair[0]>ed:\n",
    "                res+=1\n",
    "                ed=pair[1]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs.sort(key = lambda p: p[1])\n",
    "        ret = 1\n",
    "        front = pairs[0][1]\n",
    "        for p in pairs[1:]:\n",
    "            if p[0] > front :\n",
    "                ret += 1\n",
    "                front = p[1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\r\n",
    "        # dp[i]表示以pairs[i]为最后一个数对的最长的数对链\r\n",
    "        pairs = sorted(pairs, key=lambda x: x[0])\r\n",
    "        # print(pairs)\r\n",
    "        n = len(pairs)\r\n",
    "        dp = [1] * n\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(0,i):\r\n",
    "                if pairs[i][0] > pairs[j][1]:\r\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\r\n",
    "        # print(dp)\r\n",
    "        return max(dp)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        n =len(pairs)\n",
    "        if n==0: return 0\n",
    "        pairs.sort(key=operator.itemgetter(1))\n",
    "        res=1\n",
    "        right = pairs[0][1]\n",
    "        for i in range(1,len(pairs)):\n",
    "            if pairs[i][0]>right:\n",
    "                res+=1\n",
    "                right=pairs[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs.sort()\n",
    "        n = pairs[0][1]\n",
    "        ans = 1\n",
    "        for x,y in pairs:\n",
    "            if x > n:\n",
    "                n = y\n",
    "                ans += 1\n",
    "            if (y < n):\n",
    "                n = y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs.sort(key=lambda p: p[1])\n",
    "        # 数对链中最后一个数对的右端点\n",
    "        right = float('-inf')\n",
    "        maxLen = 0\n",
    "        for u, v in pairs:\n",
    "            if right < u:\n",
    "                right = v\n",
    "                maxLen += 1\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs.sort(key = lambda pair:pair[0])\n",
    "        result = [1 for i in pairs]\n",
    "        for i in range(1,len(pairs)):\n",
    "            for j in range(i):\n",
    "                if(pairs[i][0] >pairs[j][1] ):\n",
    "                    result[i] = max(result[i],result[j] + 1)\n",
    "        print(result)\n",
    "        return max(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        if len(pairs)==1:return 1\n",
    "        if len(pairs)==2:\n",
    "            if pairs[0][1]<pairs[1][0]:return 2\n",
    "            else:return 1\n",
    "        dp=[0 for i in range(len(pairs))]\n",
    "        dp[0]=1\n",
    "        pairs.sort(key=lambda x:x[0])\n",
    "        for i in range(1,len(pairs)):\n",
    "            if pairs[i-1][1]<pairs[i][0]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "                continue\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if pairs[j][1]<pairs[i][0]:\n",
    "                #if pairs[j][1]<pairs[i][0] and pairs[j+1][0]>pairs[i][1]:\n",
    "                    dp[i]=dp[j]+1\n",
    "                    break\n",
    "            if dp[i]==0:\n",
    "                dp[i]=1\n",
    "        print(pairs)\n",
    "        print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        # pairs.sort()\n",
    "        # n = len(pairs)\n",
    "        # dp = [1]*n\n",
    "        # for i in range(1, n):\n",
    "        #     for k in range(i):\n",
    "        #         if pairs[i][0] > pairs[k][1]:\n",
    "        #             dp[i] = dp[k] + 1    \n",
    "        # return max(dp)\n",
    "\n",
    "        def half_search(nums, l, r, target):\n",
    "            while l<=r:\n",
    "                m = (r-l)//2+l\n",
    "                if nums[m] == target:\n",
    "                    return m\n",
    "                elif nums[m] < target:\n",
    "                    l = m + 1\n",
    "                else: \n",
    "                    r = m - 1\n",
    "            return l\n",
    "        pairs.sort()\n",
    "        dp = [pairs[0][1]]\n",
    "        for x, y in pairs[1:]:\n",
    "            if x > dp[-1]:\n",
    "                dp.append(y)\n",
    "            else:\n",
    "                i = half_search(dp, 0, len(dp)-1, x)\n",
    "                if i < len(dp):\n",
    "                    dp[i] = min(y, dp[i])\n",
    "            print(x,y)\n",
    "            print(dp)\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: list[list[int]]) -> int:\n",
    "\n",
    "        due_ord=SortedList()\n",
    "        lens=0\n",
    "        ends=0\n",
    "        for i in pairs:\n",
    "            due_ord.add((i[1],i[0]))\n",
    "        if len(due_ord)==0:\n",
    "            return 0\n",
    "        lens+=1\n",
    "        tmp=due_ord.pop(0)\n",
    "        ends=tmp[0]\n",
    "        while len(due_ord)>0:\n",
    "            tmp=due_ord.pop(0)\n",
    "            st=tmp[1]\n",
    "            ed=tmp[0]\n",
    "            if st<=ends:\n",
    "                continue\n",
    "            else:\n",
    "                lens+=1\n",
    "                ends=ed\n",
    "        return lens\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        pairs.sort()\n",
    "        n = len(pairs)\n",
    "        dp = [1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if pairs[i][0] > pairs[j][1]:\n",
    "                    dp[i] = max(dp[i], dp[j] +1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        n = len(pairs)\n",
    "        pairs.sort(key = lambda pair:pair[1])\n",
    "        result = 1\n",
    "        temp = pairs[0][1]\n",
    "        for i in range(1, n):\n",
    "            if pairs[i][0] > temp:\n",
    "                result += 1\n",
    "                temp = pairs[i][1]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestChain(self, pairs: List[List[int]]) -> int:\n",
    "        newList = sorted(pairs, key = lambda x: x[0])\n",
    "        dp = [1] * len(newList)\n",
    "        lengthmax = 1\n",
    "        for i in range(1, len(newList)):\n",
    "            for j in range(i):\n",
    "                if newList[j][1] < newList[i][0]:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "            lengthmax = max(lengthmax, dp[i])\n",
    "        return lengthmax"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
